public class LinkList {
    static class LinkNode {
        private int value;
        private LinkNode next;
        public LinkNode(int value) {
            this.value = value;
        }
    }
    public LinkNode head;
    public void creat () {
        LinkNode node1 = new LinkNode(12);
        LinkNode node2 = new LinkNode(34);
        LinkNode node3 = new LinkNode(56);
        LinkNode node4 = new LinkNode(78);
        LinkNode node5 = new LinkNode(90);
        head = node1;
        node1.next = node2;
        node2.next = node3;
        node3.next = node4;
        node4.next = node5;
    }
    //addFirst addLast addIndex contains remove removeAllkey size clear display
    public void display () {
        LinkNode cur = head;
        while(cur != null) {
            System.out.print(cur.value + " ");
            cur = cur.next;
        }
        System.out.println();
    }
    public void display (LinkNode head) {     //wu
        LinkNode cur = head;
        while(cur != null) {
            System.out.print(cur.value + " ");
            cur = cur.next;
        }
        System.out.println();
    }
    public void addFirst (int data) {
        LinkNode node = new LinkNode(data);
        node.next = head;
        head = node;
    }
    public int size () {
        int count = 0;
        LinkNode cur = head;
        while(cur != null) {
            count++;
            cur = cur.next;
        }
        return count;
    }
    public void addLast (int data) {
        LinkNode node = new LinkNode(data);
        if(head == null) {
            head = node;
            return;
        }
        LinkNode cur = head;
        while (cur.next != null) {
            cur = cur.next;
        }
        cur.next = node;
    }
    public boolean contains (int key) {
        LinkNode cur = head;
        while(cur != null) {            //wu
            if(cur.value == key)
                return true;
            cur = cur.next;
        }
        return false;
    }
    public void remove (int key) {
        if(head == null)
            return;
        if(head.value == key) {
            head = head.next;
            return;
        }
        LinkNode cur = head;
        while (cur.next != null) {
            if(cur.next.value == key) {
                break;
            }
            cur = cur.next;
        }
        if(cur.next == null) {
            System.out.println("不存在");
            return;
        }
        cur.next = cur.next.next;
    }
    public void addIndex (int index, int data) {
        if (index < 0 || index > size()) {
            System.out.println("超出范围");
            return;
        }
        if(index == 0) {
            addFirst(data);
            return;
        }
        if (index == size()) {
            addLast(data);
            return;
        }
        LinkNode cur = head;
        int count = 1;
        while (cur.next != null) {
            if(count == index) {
                LinkNode node = new LinkNode(data);
                node.next = cur.next;
                cur.next = node;
                return;
            }
            cur = cur.next;
        }
    }
    public void clear () {
        this.head = null;
    }
    public void removeAll (int key) {
        if(head == null) return;
        LinkNode prev = head;
        LinkNode cur = head.next;
        while (cur != null) {
            if (cur.value == key) {
                prev.next = cur.next;
                cur = cur.next;
            } else {
                prev = cur;
                cur = cur.next;
            }
        }
        if (head.value == key) {
            head = head.next;
        }
    }
    public  void creatCycle () {
        LinkNode cur = this.head;
        while (cur.next != null) {
            cur = cur.next;
        }
        cur.next = head.next.next.next;
    }
    public  LinkNode findStart (LinkNode head) {
        if (head == null) return null;
        LinkNode f = head;
        LinkNode s = head;
        while (f != null && f.next != null) {
            f = f.next.next;
            s = s.next;
            if (s == f)
                break;
        }
        if (f == null || f.next == null) return null;
        f = head;
        while (f != s) {
            f = f.next;
            s = s.next;
        }
        return f;
    }

    public static void main(String[] args) {
        LinkList linkList = new LinkList();
        linkList.addLast(1);
        linkList.addLast(2);
        linkList.addLast(3);
        linkList.addLast(4);
        linkList.addLast(5);
        linkList.addLast(6);
        linkList.addLast(7);
        linkList.addLast(8);
        linkList.addLast(9);
        linkList.creatCycle();
        System.out.println(linkList.findStart(linkList.head).value);
    }
}
